package com.my.code.algorithm;

import com.my.code.sort.Util;

/**
 * <b>求数组中位数</b><p>
 * 使用快速排序算法
 * @author zzl
 * @date 2020/10/23
 */
public class TestMid {

    public static void main(String[] args) {
        int[] arr = {6, 7, 3, 1, 5};
        int mid = findMid(arr);
        System.out.println("mid = " + mid);
    }

    private static int findMid(int[] arr) {
        int start = 0, end = arr.length - 1;
        int mid = end / 2;
        int sp = split(arr, start, end);
        while (sp != mid) {//利用分治思想，直到支点的位置是数组中间
            if (mid < sp) {
                sp = split(arr, start, sp - 1);
            } else sp = split(arr, sp + 1, end);
        }
        return arr[mid];
    }

    private static int split(int[] arr, int start, int end) {
        int base = arr[start];
        int i = start, j = end;

        while (i < j) {
            while (i < j && arr[j] >= base) j--;
            while (i < j && arr[i] <= base) i++;
            if (i != j) {
                Util.swap(arr, i, j);
            }
        }
        Util.swap(arr, i, start);
        return i;
    }

}
